package org.labuladong.动态规划算法.二维DP;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-22:28
 * @Description:
 * 给你⼀个只包含正整数的⾮空数组 nums。请你判断是否可以将这个数组分割成两个⼦集，使得两个⼦集的元
 * 素和相等。
 * 示例 1：
 * 输⼊：nums = [1,5,11,5]
 * 输出：true
 * 解释：数组可以分割成 [1, 5, 5] 和 [11]。
 *
 * @version: 1.0
 */
public class LC_416_分割等和子集 {
	public static void main(String[] args) {
		int[] nums = {1,5,11,5};
		System.out.println(canPartition(nums));
	}

	public static boolean canPartition(int[] nums) {
		int sum = 0;
		for (int num : nums) sum += num;
		// 和为奇数时，不可能划分成两个和相等的集合
		if (sum % 2 != 0) return false;
		int n = nums.length;
		sum = sum / 2;
		boolean[][] dp = new boolean[n + 1][sum + 1];
		// base case
		for (int i = 0; i <= n; i++)
			dp[i][0] = true;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= sum; j++) {
				if (j - nums[i - 1] < 0) {
					// 背包容量不⾜，不能装⼊第 i 个物品
					dp[i][j] = dp[i - 1][j];
				} else {
					// 装⼊或不装⼊背包
					dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
				}
			}
		}
		return dp[n][sum];
	}
}
